package leetcode.array_sort;

/**
 * 75. 颜色分类
 * <p>
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * <p>
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * <p>
 * 注意:
 * 不能使用代码库中的排序函数来解决这道题。
 * <p>
 * 示例:
 * <p>
 * 输入: [2,0,2,1,1,0]
 * 输出: [0,0,1,1,2,2]
 * 分析：说明只有三个元素，0,1,2 我们可以使用开辟一个三个大小数组的方式进行存储相应元素的频率 比如 o-2 ，1-2 ，2-2  数组索引和频率关联
 * 当然也可以使用三路快拍思想进行处理，大于 1的都放在数组的右边，小于1的放到数组的左边
 */
public class Solution75 {
    public static void sortColors(int[] nums) {
        partition(nums, 0, nums.length - 1);
    }

    //定义 lt gt l r  使得满足  [l,lt]<1 [lt+1,gt-1] =1  [gt,r]>1
    private static void partition(int[] arr, int l, int r) {
        int lt = l - 1; //初始化时需要满足自己定义的关系 为空 满足定义
        int gt = r + 1; //为空
        int i = l; //i指向下一个需要判断的元素
        while (i < gt) { //因为这里的gt已经被操作过了
            if (arr[i] < 1) {
                lt++;
                swap(arr, lt, i);
                i++;
            } else if (arr[i] > 1) {//与gt--元素交换位置，则i位置元素又为没有判断的元素，所以i不需要进行i--
                gt--;
                swap(arr, i, gt);
            } else {
                i++;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {2, 0, 2, 1, 1, 0};
        sortColors(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");

    }
}
